/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 * @author matías
 * @author sergio
 */
public class HeapBinary
{

    int comparacionesLlave;
    int last;
    int n;
    Integer[] A;
    String archivoSalida;
    private long tiempo;

    public HeapBinary ( int n , String salida )
    {
        this.n = n;
        this.archivoSalida = salida;
        this.A = new Integer[ n + 1 ];
        this.A[0] = Integer.MIN_VALUE;
        this.last = 0;
        this.comparacionesLlave = 0;
    }

    public void Insert ( Integer elem )
    {
        this.last = this.last + 1;
        int aux = this.last, parent = aux / 2;
        while ( elem < this.A[parent] )
        {
            this.comparacionesLlave += 1;
            this.A[aux] = this.A[parent];
            aux = parent;
            parent = aux / 2;
        }
        this.A[aux] = elem;
    }

    private Integer findMin ( boolean mostrar )
    {
        if ( this.last == 0 )
        {
            if ( mostrar )
            {
                System.out.println ( "FindMin: last " + this.last + " ==0" );
            }
            return null;
        }
        return this.A[1];
    }

    public Integer extractMin ( boolean mostrar )
    {
        if ( this.last == 0 )
        {
            System.out.println ( "ExtractMin: Last " + last + " ==0" );
            return null;

        }
        Integer elem = this.A[1];
        this.A[1] = this.A[last];
        this.last = this.last - 1;
        percolateDown ( 1 , mostrar );
        return elem;
    }

    private void percolateDown ( int pos , boolean mostrar )
    {
        Integer aux = this.A[pos];
        Integer smaller;
        while ( true )
        {
            Integer leftChild = 2 * pos, rightChild = leftChild + 1;
            if ( leftChild > this.last )
            {
                if ( mostrar )
                {
                    System.out.println ( "PercolateDown: leftChild = " + leftChild + " > " + "last =" + last );
                }
                break;
            }
            else if ( leftChild == this.last || this.A[leftChild] < A[rightChild] )
            {
                smaller = leftChild;
                if ( mostrar )
                {
                    System.out.println ( "PercolateDown: leftChild = " + leftChild + "==" + "last " + last );
                    System.out.println ( "o A(leftchild) < A(rightChild)" );
                }
                this.comparacionesLlave += 1;
            }
            else
            {
                smaller = rightChild;
            }
            if ( this.A[smaller] < aux )
            {
                this.A[pos] = A[smaller];
                if ( mostrar )
                {
                    System.out.println ( "PercolateDown:  A(Smaller)= " + this.A[smaller] + " <  Aux= " + aux );
                }
                this.comparacionesLlave += 1;
                pos = smaller;
            }
            else
            {
                break;
            }
        }
        this.A[pos] = aux;
    }

    public void Floyd ( Integer[] l , boolean mostrar )
    {
        if ( l.length > 0 )
        {
            if ( mostrar )
            {
                System.out.println ( "Floyd : l.lenght = " + l.length + " > 0" + "   insertamos los numeros al heap" );
            }

            for ( int i = 0 ; i < l.length ; i ++ )
            {
                this.A[ i + 1] = l[i];
            }
            this.last = l.length;
            for ( int i = this.last / 2 ; i >= 1 ; i -- )
            {
                percolateDown ( i , mostrar );
            }
        }
        else
        {
            System.out.println ( "No hay datos para agregar" );
        }
    }

    public Integer weneger ( boolean mostrar )
    {
        Integer aux;
        int leftC;
        int rightC;
        int hole;
        int lower;
        if ( last == 0 )
        {
            if ( mostrar )
            {
                System.out.println ( "Weneger:  last = " + last + " ==  0" );
            }
            return null;
        }
        if ( last == 1 )
        {
            if ( mostrar )
            {
                System.out.println ( "Weneger :  Last = " + last + " == 1" );
            }

            aux = this.A[1];
            last = last - 1;
            return aux;
        }
        aux = A[1];
        hole = 1;
        //parte 1 bajamos Hole
        while ( true )
        {
            leftC = 2 * hole;
            rightC = leftC + 1;
            if ( leftC > last )
            {
                if ( mostrar )
                {
                    System.out.println ( "Weneger: leftChild = " + leftC + " > " + "last =" + last );
                }
                break;
            }
            if ( leftC == last || A[leftC] < A[rightC] )
            {
                if ( mostrar )
                {
                    System.out.println ( "Weneger: leftChild = " + leftC + "==" + "last " + last );
                    System.out.println ( "o    A(leftchild) < A(rightChild)" );
                }

                lower = leftC;
            }
            else
            {
                lower = rightC;
            }
            this.comparacionesLlave += 1;
            A[hole] = A[lower];
            hole = lower;

        }
        //parte 2: recupar la condicion de Heap, rellenar el Hole
        while ( true )
        {
            int parent = hole / 2;
            this.comparacionesLlave += 1;
            if ( A[last] < A[parent] )
            {
                if ( mostrar )
                {
                    System.out.println ( "Weneger :  A(last) = " + A[last] + " < " + "A(parent) = " + A[parent] );
                }
                A[hole] = A[parent];
                hole = parent;
            }
            else
            {
                A[hole] = A[last];
                last = last - 1;
                break;
            }
        }
        return aux;
    }

    private void setTime ()
    {
        tiempo = System.currentTimeMillis ();
    }

    private void updateTime ()
    {
        tiempo = System.currentTimeMillis () - tiempo;
    }

    private void printTime ()
    {
        print ( "Time : " + tiempo + " miliseg" );
    }

    public void print ( String salida )
    {
        EscribirArchivo.Escribir ( archivoSalida , salida );
    }

    public boolean heapSort ( String letra , Integer[] l , boolean mostrar )
    {
        this.last = 0;
        setTime ();
        switch ( letra )
        {
            case "S":
                heapSortS ( l , mostrar );
                break;

            case "F":
                heapSortF ( l , mostrar );
                break;

            case "W":
                heapSortW ( l , mostrar );
                break;

            case "WF":
                heapSortWF ( l , mostrar );
                break;

            default:
                return false;
        }
        updateTime ();
        printTime ();

        return true;
    }

    public void heapSortS ( Integer[] l , boolean mostrar )
    {
        for ( int i = 0 ; i < l.length ; i ++ )
        {
            Insert ( l[i] );
        }
        while ( last != 0 )
        {
            print ( extractMin ( mostrar ).toString () );
        }
    }

    public void heapSortF ( Integer[] l , boolean mostrar )
    {

        Floyd ( l , mostrar );

        while ( last != 0 )
        {
            print ( extractMin ( mostrar ).toString () );
        }
    }

    public void heapSortW ( Integer[] l , boolean mostrar )
    {
        for ( int i = 0 ; i < l.length ; i ++ )
        {
            Insert ( l[i] );
        }
        while ( last != 0 )
        {

            print ( weneger ( mostrar ).toString () );

        }
    }

    public void heapSortWF ( Integer[] l , boolean mostrar )
    {

        Floyd ( l , mostrar );

        while ( last != 0 )
        {

            print ( weneger ( mostrar ).toString () );
        }
    }

    public int returnKeyCounter ()
    {
        return this.comparacionesLlave;
    }
}
